The amount of information circulating in an office network increases every year, and importance of a communication service intended for corporate users has become increasingly higher. Then, telecommunications carriers install communication networks for connecting in-house LANs (Local Area Networks) arranged at multiple bases for the corporate users and provide a band guarantee service that secures a band for every corporate user. As one example, they advance introduction of the communication system to which MPLS-TP (Multi Protocol Label Switching-Transport Profile) that realizes band guarantee is applied by establishing a path whose bandwidth is secured in advance in an end-to-end manner.
Moreover, with expansion of a demand for the communication services intended for corporate users, there are required realization of a wide band that is for increasing management efficiency of communication services intended for a large number of corporate users and high reliability that is for communicating important data (e.g., user data) surely. Furthermore, in order to reduce a maintenance cost of the communication system, power consumption reduction of each communication device with which the communication system is equipped is demanded.
The telecommunications carriers are considering introduction of a band guarantee technology that supports 100 Gbps (Gigabit per second) high speed communication. In order to realize high speed communication, each communication device converts a value of the user ID (the user Identifier) specified by an administrator of a telecommunications carrier's network into an internal ID (an internal Identifier) handled within the device at high speed.
For example, in the above-mentioned MPLS-TP, a range that a value of the user ID can take is provided to be 20 bits, i.e., a maximum of 1,048,575 as a standard code. Therefore, the user ID specified by the administrator of the telecommunications carrier's network is a 20-bit value, and the same 20-bit value is given to a main signal frame. However, the number of users managed by the communication system is generally smaller than 1,048,575. Therefore, in each communication device, a high speed communication is efficiently realized by changing the user ID specified by the administrator of the telecommunications carrier's network into the internal ID whose range of allowable values is a number manageable by the communication device.
A system is known that realizes a processing of converting the user ID into the internal ID at high speed by using CAM (Content Addressable Memory). However, since the chip on which CAM is mounted has a large power consumption, it comes with a problem that a maintenance cost of the communication system becomes large. As a technology for solving this problem, a technology disclosed in Japanese Unexamined Patent Application Publication (Translation of PCT Application) No. 2003-510963 is known.
Japanese Unexamined Patent Application Publication (Translation of PCT Application) No. 2003-510963 discloses a system of converting the user ID into the internal ID at high speed by using a hash function of compressing a value range without using CAM.
Generally, in the case of using the hash function, there occurs an event where an identical output value is outputted to multiple input values, i.e., what is called a collision. On the other hand, according to the technology disclosed by Japanese Unexamined Patent Application Publication (Translation of PCT Application) No. 2003-510963, it is possible to reduce an occurrence probability of the collision and to determine the internal ID at high speed by performing a parallel processing using multiple hash functions.
Incidentally, in the technology disclosed by Japanese Unexamined Patent Application Publication (Translation of PCT Application) No. 2003-510963, multiple entry tables (hash tables) are used when converting the user ID into the internal ID. The entry table manages a correspondence between the user ID and the internal ID for every user, i.e., information on identifier conversion for every user. In setting a new user's entry (a new entry) in this entry table, the correspondence between the user ID of the new user and the internal ID is set in a portion in which entry setting is possible in the entry table.
On the other hand, if there is no portion in which the entry setting is possible in the entry table, a set-up entry that has already been set up is relocated, and subsequently the new entry is set up. Incidentally, the case where there is no portion in which entry setting is possible is a case where the number of entries already set up is larger than the number of entry tables, that is, a case where the new entry cannot be set up in any of the entry tables.